﻿

using System.Collections.Generic;
using System.Linq;
using UnityEngine;
namespace GameGraphics.HomeWorld
{
    public class GridNode
    {
        /// <summary>
        /// 索引
        /// </summary>
        public Vector2Int Index;
        /// <summary>
        /// 上一个节点
        /// </summary>
        public GridNode Parent;

        /// <summary>
        /// 估值
        /// </summary>
        private int _f = 0;
        public int F => _f;

        /// <summary>
        /// g(n) 指的是从起始格子到格子n的实际代价
        /// </summary>
        private int _g = 0;
        public int G
        {
            get => _g;
            set
            {
                _g = value;
                _f = _g + _h;
            }
        }

        /// <summary>
        /// h(n) 指的是从格子n到终点格子的估计代价
        /// </summary>
        private int _h = 0;
        public int H
        {
            get => _h;
            set
            {
                _h = value;
                _f = _g + _h;
            }
        }

        /// <summary>
        /// 构造
        /// </summary>
        public GridNode(Vector2Int index, GridNode parent, int g, int h)
        {
            Index = index;
            Parent = parent;
            _g = g;
            _h = h;
            _f = _g + _h;
        }
    }

    public class AStar
    {
        /// <summary>
        /// 地图尺寸
        /// </summary>
        private static Vector2Int _mapSize;
        /// <summary>
        /// 地图中的所有网格
        /// </summary>
        private static int[,] _mapCells;
        /// <summary>
        /// 终点
        /// </summary>
        private static Vector2Int _endPoint;
        /// <summary>
        /// 找到的终节点
        /// </summary>
        private static GridNode _endPointNode;
        /// <summary>
        /// 准备处理的格子
        /// </summary>
        private static Dictionary<Vector2Int, GridNode> _openDict = new Dictionary<Vector2Int, GridNode>();
        /// <summary>
        /// 处理完的格子
        /// </summary>
        private static Dictionary<Vector2Int, GridNode> _closeDict = new Dictionary<Vector2Int, GridNode>();
        /// <summary>
        /// 相邻节点的相对坐标列表
        /// </summary>
        public static List<Vector2Int> _neighborRelativeCoordinateList = new List<Vector2Int>() { new Vector2Int(1, 0), new Vector2Int(-1, 0), new Vector2Int(0, 1), new Vector2Int(0, -1), new Vector2Int(1, -1), new Vector2Int(-1, 1) };

        /// <summary>
        /// 初始化
        /// </summary>
        public static List<Vector2Int> Find(int[,] mapCells, Vector2Int mapSize, Vector2Int startPoint, Vector2Int endPoint)
        {
            //Debuger.Log($"寻路 Start:{startPoint} => End:{endPoint}");
            _mapCells = mapCells;
            _mapSize = mapSize;
            _endPoint = endPoint;
            _openDict.Clear();
            _closeDict.Clear();
            _endPointNode = null;
            AddNodeInOpenList(new GridNode(startPoint, null, 0, 0));

            while (_openDict.Count > 0 && _endPointNode == null)
            {
                //先按照f的值升序排列，当f值相等时再按照h的值升序排列
                _openDict = _openDict.OrderBy(kv => kv.Value.F).ThenBy(kv => kv.Value.H).ToDictionary(p => p.Key, o => o.Value);
                //提取排序后的第一个节点
                var node = _openDict.First().Value;
                //因为使用的不是Queue，因此要从open中手动删除该节点
                _openDict.Remove(node.Index);
                //处理该节点相邻的节点
                OperateNeighborNode(node);
                //处理完后将该节点加入close中
                AddNodeInCloseList(node);
            }
            if (_endPointNode == null)
            {
                return null;
            }
            else
            {
                var list = new List<Vector2Int>();
                var node = _endPointNode;
                while (node != null)
                {
                    list.Add(node.Index);
                    node = node.Parent;
                }
                return list;
            }
        }

        /// <summary>
        /// 处理相邻的节点
        /// </summary>
        /// <param name="node"></param>
        private static void OperateNeighborNode(GridNode node)
        {
            var coordinateX = node.Index.x - node.Index.y / 2;
            var coordinateY = node.Index.y;
            for (var i = 0; i < _neighborRelativeCoordinateList.Count; i++)
            {
                var point = _neighborRelativeCoordinateList[i];
                var x = point.x + coordinateX;
                var y = point.y + coordinateY;
                var pos = new Vector2Int(x + y / 2, y);
                //超出地图范围
                if (pos.x < 0 || pos.x >= _mapSize.x || pos.y < 0 || pos.y >= _mapSize.y)
                {
                    continue;
                }
                //已经处理过的节点
                if (_closeDict.ContainsKey(pos))
                    continue;
                //障碍物节点
                if (_mapCells[pos.x, pos.y] > 0)
                    continue;
                //将相邻节点加入open中
                AddNodeInOpenList(node, pos, 1);
            }
        }

        /// <summary>
        /// 将节点加入到open中
        /// </summary>
        /// <param name="parentNode"></param>
        /// <param name="position"></param>
        /// <param name="g"></param>
        private static void AddNodeInOpenList(GridNode parentNode, Vector2Int position, int g)
        {
            //当前节点的实际距离g等于上个节点的实际距离加上自己到上个节点的实际距离
            int nodeG = parentNode.G + g;
            //如果该位置的节点已经在open中
            if (_openDict.ContainsKey(position))
            {
                //比较实际距离g的值，用更小的值替换
                if (nodeG < _openDict[position].G)
                {
                    _openDict[position].G = nodeG;
                    _openDict[position].Parent = parentNode;
                }
            }
            else
            {
                //生成新的节点并加入到open中
                var node = new GridNode(position, parentNode, nodeG, GetH(position));
                //如果周边有一个是终点，那么说明已经找到了。
                if (position == _endPoint)
                {
                    _endPointNode = node;
                }
                else
                {
                    AddNodeInOpenList(node);
                }
            }
        }

        /// <summary>
        /// 获取估价距离
        /// 曼哈顿算法
        /// </summary>
        /// <param name="position"></param>
        /// <returns></returns>
        private static int GetH(Vector2Int position)
        {
            //转成六边形下的RQS坐标
            var r1 = _endPoint.x - _endPoint.y / 2;
            var q1 = _endPoint.y;
            var s1 = -r1 - q1;
            var r2 = position.x - position.y / 2;
            var q2 = position.y;
            var s2 = -r2 - q2;
            return Mathf.Max(Mathf.Abs(r1 - r2), Mathf.Abs(q1 - q2), Mathf.Abs(s1 - s2));
        }

        /// <summary>
        /// 添加节点到Open列表
        /// </summary>
        /// <param name="node"></param>
        private static void AddNodeInOpenList(GridNode node)
        {
            _openDict[node.Index] = node;
        }

        /// <summary>
        /// 添加节点到close列表
        /// </summary>
        /// <param name="node"></param>
        private static void AddNodeInCloseList(GridNode node)
        {
            _closeDict.Add(node.Index, node);
        }
    }
}
